package LeetCode._02_数组;

import java.util.PriorityQueue;

public class _215_数组中的第K个最大元素 {
    //小顶堆实现
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0) return -1;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.offer(num);
            if(heap.size()>k){
                heap.poll();
            }
        }
        return heap.peek();
    }

    //快速排序实现
    public int findKthLargestQ(int[] nums, int k) {
        if(nums == null || nums.length == 0) return -1;
        int lo = 0,hi = nums.length - 1;
        k = nums.length - k; //第K大的元素
        while(lo<=hi){
            int p = partition(nums,lo,hi);
            if(p<k){
                lo = p + 1;
            }else if(p>k){
                hi = p - 1;
            }else{
                return nums[p];
            }
        }
        return -1;
    }

    private static int partition(int[] nums,int lo,int hi){
        swap(nums,lo,lo +(int)(Math.random())*(hi - lo));
        int pivot = nums[lo];
        while(lo<=hi){
            while(lo<=hi){
                if(cmp(pivot,nums[hi])<0){
                    hi--;
                }else{
                    nums[lo++] = nums[hi];
                    break;
                }
            }
            while(lo<=hi){
                if(cmp(pivot,nums[lo])>0){
                    lo++;
                }else{
                    nums[hi--] = nums[lo];
                    break;
                }
            }
        }
        nums[lo] = pivot;
        return lo;
    }

    private static int cmp(int i,int j){
        return i - j;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
